#include <iostream>
#include <limits>
#include <stack>

#include "Edge.h"
#include "Graph.h"
#include "SpanningTree.h"

using namespace std;


Graph* LoadData(const string& fileName);
void PrintGraph(Graph* g);
void PrintSpanningTree(SpanningTree* s);

int main() {
	const int minBound = 2;
	
	Graph* graph = LoadData("D:\\CVUT\\MAGISTR\\MI-PAR\\semestralka\\CSharp_implementace\\vstup.txt");
	PrintGraph(graph);

	int startNode = 0;
	int minDegree = numeric_limits<int>::max();
	vector<Edge> minSpanningTree;

	SpanningTree* spanningTree = new SpanningTree(graph->NodesCount, startNode);
	stack<Edge*> myStack;

	//uvodni naplneni zasobniku
	int i;
	for(i=0; i < graph->AdjacencyList[startNode].size(); i++)
	{
		int adjacent = graph->AdjacencyList[startNode][i];
		myStack.push(new Edge(startNode, adjacent, false));
	}

	Edge* currentEdge;

	while(!myStack.empty())
	{
		currentEdge = myStack.top();
		if(!currentEdge->IsVisited)
		{
			currentEdge->IsVisited = true;
			spanningTree->AddEdge(currentEdge);

			int spanningTreeDegree = spanningTree->GetDegree();
			if(spanningTreeDegree >= minDegree)
			{
				continue;
			}

			if(spanningTree->IsSpanningTree())
			{
				PrintSpanningTree(spanningTree);
				if(spanningTreeDegree < minDegree)
				{	
					minDegree = spanningTreeDegree;
					minSpanningTree.clear();
					int i;
					for (i=0; i < spanningTree->Edges.size(); i++) 
					{
						minSpanningTree.push_back(Edge(spanningTree->Edges[i]->FromNode, spanningTree->Edges[i]->ToNode,false));
					}
				}
				if(spanningTreeDegree == minBound)
				{
					break;
				}
			}

			//projde vsechny sousedy (v zadanem grafu) vsech uzlu co jsou v kostre a prida
            //na zasobnik hrany vedouci z uzlu v kostre do souseda tohoto uzlu v zadanem grafu
            //ktery jeste v kostre neni
			set<int>::iterator it;
			int i;
			for (it=spanningTree->Nodes.begin(); it!=spanningTree->Nodes.end(); ++it)
			{

				int treeNode = *it;
				for(i=0; i < graph->AdjacencyList[treeNode].size(); i++)
				{
					int adjacent = graph->AdjacencyList[treeNode][i];
					if(spanningTree->Nodes.find(adjacent) == spanningTree->Nodes.end())
					{
						myStack.push(new Edge(treeNode, adjacent, false));
					}
				}
			}

			
		}
		else
		{
			myStack.pop();
			spanningTree->RemoveEdge(currentEdge);
			delete currentEdge;
		}
	}

	//deleting
	delete graph;
	delete spanningTree;

	cout << "Minimum degree: " << minDegree << endl;
	cout << "Spanning Tree:" << endl;
	for (i=0; i < minSpanningTree.size(); i++) 
	{
		cout << minSpanningTree[i].FromNode << "->" << minSpanningTree[i].ToNode << endl;
	}
	
	char a;
	cin >> a;
}


void PrintGraph(Graph* g) {
	cout << "Nodes Count: " << g->NodesCount << endl;
	int i,j;
	for(i=0; i < g->AdjacencyList.size(); i++)
    {
		for(j=0; j < g->AdjacencyList[i].size(); j++)
		{
			cout << g->AdjacencyList[i][j];
		}
		cout << endl;
    }
}


void PrintSpanningTree(SpanningTree* s) {
	cout << "Edges in spanning tree:" << endl;
	int i;
	for(i=0; i < s->Edges.size(); i++)
    {
		cout << s->Edges[i]->FromNode << "->" << s->Edges[i]->ToNode << endl;
    }
}

Graph* LoadData(const string& fileName) {
	ifstream infile;
	infile.open(fileName);

	if(!infile) { 
		cout << "Cannot open file.\n"; 
		return NULL; 
	} 

	Graph* g = new Graph(infile); 
	
	infile.close();

	return g;
}